package com.fr.lintcode;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/**
*作者：furong
*日期：2017年3月24日
*时间：下午5:22:58
*/
public class Q473 {
    class WordDictionary {
        Dic node = new Dic();

        public void addWord(String word) {
            Dic tmp = node;
            for (char c : word.toCharArray()) {
                Dic d = tmp.child.get(c);
                if (d == null) {
                    d = new Dic();
                    d.c = c;
                    tmp.child.put(c, d);
                }
                tmp = d;
            }
            tmp.isEnd = true;
        }

        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        boolean hasWord = false;

        public boolean search(String word) {
            hasWord = false;
            search(node, word, 0);
            return hasWord;
        }

        private void search(Dic node, String word, int index) {
            if (hasWord) {
                return;
            }
            if (word.length() == index) {
                if (node != null) {
                    hasWord = node.isEnd;
                    return;
                }
            }
            if (node == null) {
                return;
            }
            char c = word.charAt(index);
            if (c == '.') {
                for (Dic d : node.child.values()) {
                    search(d, word, index + 1);
                }
            } else {
                Dic tmp = node.child.get(c);
                search(tmp, word, index + 1);
            }
        }

        class Dic {
            char c;
            Map<Character, Dic> child = new HashMap<>();
            boolean isEnd;
        }
    }

    @Test
    public void testA() {
        WordDictionary w = new WordDictionary();
        w.addWord("bad");
        w.addWord("dad");
        w.addWord("mad");
        System.out.println(w.search("pad")); // return false
        System.out.println(w.search("bad")); // return true
        System.out.println(w.search(".ad")); // return true
        System.out.println(w.search("b.."));// return true

    }

}
